#ifndef SEARCHTREE_H
#define SEARCHTREE_H

#include "prep.h"
#include <wx/string.h>
#include <vector>
#include <map>
#include <set>

typedef size_t nSearchTreeNode;
typedef size_t nSearchTreeLabel;
class SearchTreeNode;
class BasicSearchTree;
class SearchTreePoint;
typedef std::map<wxChar, nSearchTreeNode, std::less<wxChar> > SearchTreeLinkMap;
typedef std::vector<SearchTreeNode*> SearchTreeNodesArray;
typedef std::vector<SearchTreePoint> SearchTreePointsArray;
typedef std::map<size_t, size_t, std::less<size_t> > SearchTreeItemsMap;
typedef std::vector<wxString> SearchTreeLabelsArray;

class BasicSearchTreeIterator {
  public:
    BasicSearchTreeIterator();
    BasicSearchTreeIterator( BasicSearchTree* tree );
    virtual ~BasicSearchTreeIterator() {}
    bool IsValid();
    bool FindPrev( bool includechildren = true );
    bool FindNext( bool includechildren = true );
    const nSearchTreeNode& operator* () const { return m_CurNode; }
    const BasicSearchTreeIterator& operator++() { FindNext(); return *this; }
    const BasicSearchTreeIterator& operator--() { FindPrev(); return *this; }
    bool FindNextSibling();
    bool FindPrevSibling();
    bool FindSibling( wxChar ch );
    bool Eof() {
      return ( !IsValid() || m_Eof );
    }
  protected:
    nSearchTreeNode  m_CurNode;
    bool m_Eof;
    BasicSearchTree* m_Tree;
    size_t m_LastTreeSize;
    SearchTreeNode*  m_LastAddedNode;
};

class SearchTreePoint {
  public:
    nSearchTreeNode n;
    size_t depth;
    SearchTreePoint(): n( 0 ), depth( 0 ) {}
    SearchTreePoint( nSearchTreeNode nn, size_t dd ) { n = nn; depth = dd; }
};

class SearchTreeNode {
    friend class BasicSearchTree;
    friend class BasicSearchTreeIterator;
  public:
    SearchTreeNode();
    SearchTreeNode( unsigned int depth, nSearchTreeNode parent, nSearchTreeLabel label, unsigned int labelstart, unsigned int labellen );
    virtual ~SearchTreeNode();
    nSearchTreeNode GetParent() const {
      return m_Parent;
    }
    void SetParent( nSearchTreeNode newparent ) {
      m_Parent = newparent;
    }
    nSearchTreeNode GetChild( wxChar ch );
    size_t GetItemNo( size_t depth );
    size_t AddItemNo( size_t depth, size_t itemno );
    SearchTreeNode* GetParent( const BasicSearchTree* tree ) const;
    SearchTreeNode* GetChild( BasicSearchTree* tree, wxChar ch );
    wxString GetLabel( const BasicSearchTree* tree ) const;
    wxChar GetChar( const BasicSearchTree* tree ) const;
    const wxString& GetActualLabel( const BasicSearchTree* tree ) const;
    nSearchTreeLabel GetLabelNo() const {
      return m_Label;
    }
    unsigned int GetLabelStart() const {
      return m_LabelStart;
    }
    unsigned int GetLabelLen() const {
      return m_LabelLen;
    }
    void SetLabel( nSearchTreeLabel label, unsigned int labelstart, unsigned int labellen );
    unsigned int GetDepth() const {
      return m_Depth;
    }
    void RecalcDepth( BasicSearchTree* tree );
    void UpdateItems( BasicSearchTree* tree );
    unsigned int GetLabelStartDepth() const;
    bool IsLeaf() const { return m_Children.empty() && ( m_Depth != 0 ); }
    unsigned int GetDeepestMatchingPosition( BasicSearchTree* tree, const wxString& s, unsigned int StringStartDepth );
    wxString Serialize( BasicSearchTree* tree, nSearchTreeNode node_id, bool withchildren = false );
    void Dump( BasicSearchTree* tree, nSearchTreeNode node_id, const wxString& prefix, wxString& result );
    static wxString SerializeString( const wxString& s );
    static wxString U2S( unsigned int u );
    static wxString I2S( int i );
    static bool UnSerializeString( const wxString& s, wxString& result );
    static bool S2U( const wxString& s, unsigned int& u );
    static bool S2I( const wxString& s, int& i );
  protected:
    unsigned int m_Depth;
    nSearchTreeNode m_Parent;
    nSearchTreeLabel m_Label;
    unsigned int m_LabelStart;
    unsigned int m_LabelLen;
    SearchTreeLinkMap m_Children;
    SearchTreeItemsMap m_Items;
};

class BasicSearchTree {
    friend class SearchTreeNode;
    friend class BasicSearchTreeIterator;
  public:
    BasicSearchTree();
    virtual ~BasicSearchTree();
    virtual size_t size() const {
      return m_Points.size();
    }
    virtual size_t GetCount() const {
      return m_Points.size();
    }
    virtual void clear();
    size_t insert( const wxString& s );
    bool HasItem( const wxString& s );
    size_t count( const wxString& s ) { return HasItem( s ) ? 1 : 0; }
    size_t GetItemNo( const wxString& s );
    const wxString GetString( size_t n ) const;
    size_t FindMatches( const wxString& s, std::set<size_t>& result, bool caseSensitive, bool is_prefix );
    wxString SerializeLabels();
    wxString dump();
  protected:
    virtual SearchTreeNode* CreateNode( unsigned int depth, nSearchTreeNode parent, nSearchTreeLabel label, unsigned int labelstart, unsigned int labellen );
    wxString GetString( const SearchTreePoint& nn, nSearchTreeNode top = 0 ) const;
    SearchTreeNode* GetNode( nSearchTreeNode n, bool NullOnZero = false );
    bool FindNode( const wxString& s, nSearchTreeNode nparent, SearchTreePoint* result );
    SearchTreePoint AddNode( const wxString& s, nSearchTreeNode nparent = 0 );
    wxString SerializeLabel( nSearchTreeLabel labelno );
  private:
    void CreateRootNode();
    nSearchTreeNode SplitBranch( nSearchTreeNode n, size_t depth );
  protected:
    SearchTreeLabelsArray m_Labels;
    SearchTreeNodesArray m_Nodes;
    SearchTreePointsArray m_Points;
};

template <class T> class SearchTree : public BasicSearchTree {
  public:
    SearchTree();
    virtual ~SearchTree();
    virtual void clear();
    size_t GetCount() const;
    virtual size_t size() const;
    bool SaveCacheTo( const wxString& filename );
    bool LoadCacheFrom( const wxString& filename );
    wxString Serialize();
    T GetItem( const wxString& s );
    T GetItem( const wxChar* s );
    size_t AddItem( const wxString& s, T item, bool replaceexisting = false );
    T& GetItemAtPos( size_t i );
    void SetItemAtPos( size_t i, T item );
    T& operator[]( const wxString& s );
    virtual wxString SerializeItem( M_Code_unused size_t idx ) { return wxString( _T( "" ) ); }
  virtual void* UnserializeItem( M_Code_unused const wxString& s ) { return NULL; }  protected:
    std::vector<T> m_Items;
    virtual void ClearItems();
    virtual bool AddFirstNullItem();
};

template <class T> SearchTree<T>::SearchTree() : BasicSearchTree() {
  m_Items.clear();
  AddFirstNullItem();
}

template <class T> SearchTree<T>::~SearchTree() {
  ClearItems();
}

template <class T> void SearchTree<T>::clear() {
  ClearItems();
  BasicSearchTree::clear();
  AddFirstNullItem();
}

template <class T> size_t SearchTree<T>::GetCount() const {
  size_t result = m_Items.size() - 1;
  return result;
}

template <class T> size_t SearchTree<T>::size() const {
  size_t result = m_Items.size() - 1;
  return result;
}

template <class T> bool SearchTree<T>::SaveCacheTo( const wxString& filename ) {
  return true;
}

template <class T> bool SearchTree<T>::LoadCacheFrom( const wxString& filename ) {
  return true;
}

template <class T> T SearchTree<T>::GetItem( const wxChar* s ) {
  wxString tmps( s );
  return GetItem( tmps );
}

template <class T> T SearchTree<T>::GetItem( const wxString& s ) {
  size_t itemno = GetItemNo( s );
  if( !itemno && !s.empty() ) {
    return T();
  }
  return GetItemAtPos( itemno );
}

template <class T> size_t SearchTree<T>::AddItem( const wxString& s, T item, bool replaceexisting ) {
  size_t itemno = insert( s );
  if( itemno > m_Items.size() ) {
    m_Items.resize( itemno );
  } else if( itemno == m_Items.size() ) {
    m_Items.push_back( item );
  } else if( replaceexisting ) {
    m_Items[itemno] = item;
  }
  return itemno;
}

template <class T> T& SearchTree<T>::GetItemAtPos( size_t i ) {
  if( i >= m_Items.size() || i < 1 ) {
    i = 0;
  }
  return m_Items[i];
}

template <class T> void SearchTree<T>::SetItemAtPos( size_t i, T item ) {
  m_Items[i] = item;
}

template <class T> void SearchTree<T>::ClearItems() {
  m_Items.clear();
}

template <class T> bool SearchTree<T>::AddFirstNullItem() {
  T newvalue;
  m_Items.push_back( newvalue );
  return true;
}

template <class T> T& SearchTree<T>::operator[]( const wxString& s ) {
  size_t curpos = GetItemNo( s );
  if( !curpos ) {
    T newitem;
    curpos = AddItem( s, newitem );
  }
  return m_Items[curpos];
}

template <class T> wxString SearchTree<T>::Serialize() {
  wxString result;
  result << _T( "<SearchTree>\n" );
  result << SerializeLabels();
  result << _T( "<nodes>\n" );
  for( size_t i = 0; i < m_Nodes.size(); ++i ) {
    result << m_Nodes[i]->Serialize( this, i, false );
  }
  result << _T( "</nodes>\n" );
  result << _T( " <items>\n" );
  for( size_t i = 1; i < m_Items.size(); ++i ) {
    result << SerializeItem( i );
  }
  result << _T( " </items>\n" );
  result << _T( "</SearchTree>\n" );
  return result;
}

#endif
